//思路：对称二叉树 1）递归 后序遍历左右中传回判断结果 2）双端队列


import java.util.*;
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }



 public class Solution {
     public boolean isSymmetric(TreeNode root) {
         if(root==null) return true;
         return compare(root);
     }
     public boolean compare(TreeNode r){
         Deque<TreeNode> q=new LinkedList<>();
         q.offerFirst(r.left);
         q.offerLast(r.right);
         while(!q.isEmpty()){
             TreeNode left=q.pollFirst();
             TreeNode right=q.pollLast();
             if(left==null&&right==null) continue;
             if(left==null||right==null||left.val!=right.val) return false;
             q.offerFirst(left.right);
             q.offerFirst(left.left);
             q.offerLast(right.left);
             q.offerLast(right.right);
         }
         return true;

     }

}